//
// Created by zhuanding on 2023/5/25.
//

#include <cstdlib>
#include "../01-preface/Status.h"

typedef struct LinkNode {  // 链式队列结点
    ElemType data;
    struct LinkNode *next;
} LinkNode;
typedef struct {  // 链式队列
    LinkNode *front, *rear;   // 队列的队头和队尾指针
} *LinkQueue;


void InitQueue_L(LinkQueue &Q) {
    Q->front = Q->rear = (LinkNode *) malloc(sizeof(LinkNode));  // 建立头结点，并让头指针和队尾指针指向头结点
    Q->front->next = NULL; // 初始为空
}

bool QueueEmpty(LinkQueue Q) {
    return Q->front == Q->rear;
}

int QueueLength_L(LinkQueue Q) {
    int k = 0;
    LinkNode *p = Q->front->next;
    while (p) {
        k++;
        p = p->next;
    }
    return k;
}

bool EnQueue_L(LinkQueue &Q, ElemType e) {
    LinkNode *s = (LinkNode *) malloc(sizeof(LinkNode));  // 新建节点
    if (s == NULL) return false;
    s->data = e;
    s->next = NULL;
    Q->rear->next = s;
    Q->rear = s;
    return true;
}

bool Dequeue_L(LinkQueue &Q, ElemType &e) {
    if (Q->front == Q->rear) return false;  // 空队
    LinkNode *p = Q->front->next;
    e = p->data;
    Q->front->next = p->next;
    if (Q->rear == p)
        Q->rear == Q->front;   // 若原队列中只有一个结点，删除后变空
    free(p);
    return true;
}

bool GetHead_L(LinkQueue Q, ElemType &e) {
    if (Q->front == Q->rear) return false;  // 空队
    e = Q->front->next->data;  // 第一个结点的数据域
    return true;
}

void DestroyQueue_L(LinkQueue &Q) {
    LinkNode *p, *q;
    p = Q->front;
    while (p) {
        q = p;
        p = p->next;
        free(q);
    }
    Q->front = Q->rear = NULL;
}

int main() {
    LinkQueue Q;
    ElemType e;
    int a[10] = {0};
    printf("***********初始化链队列***********\n");
    InitQueue_L(Q);
    printf(">>>>>初始化成功！表长为%d\n", QueueLength_L(Q));
    printf("链队列Q的地址是%p\n", &Q);
    printf("\n");

    printf("***********链队列是否为空***********\n");
    if (QueueEmpty(Q)) {
        printf("链队列为空\n");
    } else {
        printf("链队列非空\n");
    }
    printf("\n");

    printf("***********入队操作***********\n");
    for (int i = 1; i <= 10; i++) {
        a[i] = i * i;
        if (EnQueue_L(Q, a[i])) {
            printf("元素%d入队成功！\n", a[i]);
            GetHead_L(Q, e);
            if (e)
                printf("队首元素为:%d\n", e);
            else
                printf("取队首元素失败！\n");
            printf("当前顺序队列的长度为：%d\n", QueueLength_L(Q));
            printf("--------\n");
        } else {
            printf("入队失败!\n");
        }
    }
    printf("\n");

    printf("***********顺序队列元素出队***********\n");
    while (!QueueEmpty(Q)) {
        Dequeue_L(Q, e);
        if (e)
            printf("%d元素出队\n", e);
        else
            printf("出队失败！\n");
    }
    printf("\n");

    printf("***********销毁链队列***********\n");
    DestroyQueue_L(Q);
    printf("\n");
    return 0;
}